class Solution {
public:
    string minWindow(string s, string t) {
        if(s.size() < t.size()) 
            return "";

        map<char, int> hs;
        map<char, int> ht;
        string ans;

        for(auto &e : t) ht[e]++;

        int left = 0;
        int cnt = 0;
        for(int i = 0; i < s.size(); i++)
        {
            hs[s[i]]++;
            // 解释一下为什么下面要<=，而不是==
            // 因为t字符串中有可能是有多个重复字符，所以s中可能还没遍历到那么多的字符，但是都是同一个字符
            // 比如s = "aab"，t = "aa"
            // 此时ht中a：2
            // 刚开始遍历s，遇到第一个a，其实cnt是应该++的，因为a算是有效字符，只不过个数还没达到，所以要用<=
            if(hs[s[i]] <= ht[s[i]])
                cnt++;

            // 这里不像之前两道题：后续插入一些没用的字符会影响窗口，在这道题是不会的
            // 这道题只有遇到超过t的某一个字符了，窗口才要右移
            // 比如s = "adfebc"，t = "abc"
            // 站在上帝视角，这道题答案肯定是adfebc，中间需要夹带无效字符的
            // 此时ht中，a：1，b：1，c：1
            // hs中a：1，cnt++
            // 遇到d，此时hs中a：1，d：1，下面的while循环条件依然不满足，只有再遇到一个a，窗口才需右移

            // 这道题这里也要用while
            // 比如s = "ADBECOEBANC"， t = "ABC"
            // 第一次收获结果是ans = "ADBEC"，此时还是往后遍历，比如是"ADBECO"，因为这里已经不符合最小覆盖子串了，所以下面的ans并不会更新
            // 所以得遇到left指向的字符超过t中的left指向的字符才会执行这里的while，此时left指向的字符还是a，也就是s的第一个元素
            // 此时已经遍历到ADBECOEBA，hs中A：2 > ht中A：1
            // 此时触发循环条件A，D，B，E这些字符都大于t中相应字符数量

            // 执行完整个循环之后(遇到C就停止了，因为C在ht中也是1)，所以hs中剩C：1，O：1，E：1，B：1，A：1

            // 此时left指向C，也就是4，i此时是第二个A，也就是8，下面i-left+1 = 8-4+1 = 5，和之前的ans的个数相等，并不会更新ans
            // 直到遇到最后一个C，因为刚好触发上面left指向的C在hs中等于2，已经大于ht中C的值了，再次触发while循环，直到left指向B(倒数第四个)
            // 这时，下面的i-left+1 = 10-7+1 = 4，比上次的ans小，更新ans为"BANC"

            // if(hs[s[left]] > ht[s[left]])
            while(hs[s[left]] > ht[s[left]])
            {
                hs[s[left]]--;
                left++;
            }

            if(cnt == t.size())
            {
                if(ans.empty() || ans.size() > i - left + 1)
                    ans = s.substr(left, i - left + 1);
                // cout << s.substr(left, i - left + 1) << endl;
            }

        }
        return ans;
    }
};